package com.leetcode.双周赛.第44场;

/**
 * @author: xiaomi
 * @date: 2021/1/23
 * @description: 5646. 需要教语言的最少人数
 * https://leetcode-cn.com/contest/biweekly-contest-44/problems/minimum-number-of-people-to-teach/
 */
public class B_5646_需要教语言的最少人数 {

    public static void main(String[] args) {
        int n = 2;
        int[][] language = {{1}, {2}, {1, 2}};
        int[][] friendships = {{1, 2}, {1, 3}, {2, 3}};
        B_5646_需要教语言的最少人数 action = new B_5646_需要教语言的最少人数();
        action.minimumTeachings(n, language, friendships);
    }

    /**
     * 刚开始以为是连通问题，但是似乎又不是
     * --
     * 暴力解法
     * 1.遍历好友关系来确认最需要的一种语言；
     * 2.利用 map 统计最少需要的
     *
     * @param n           语言的种类
     * @param languages   每个人掌握的语言
     * @param friendships 好友关系
     * @return
     */
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int len = friendships.length;
        int[] lanCount = new int[n];
        for (int i = 0; i < len; i++) {
            //第一个人掌握的语言
            int[] p1l = languages[friendships[i][0]];
            int[] p2l = languages[friendships[i][1]];
            boolean isSame = false;
            for (int j = 0; j < p1l.length; j++) {
                if (isSame) {
                    break;
                }
                for (int k = 0; k < p2l.length; k++) {
                    if (p1l[j] == p2l[k]) {
                        isSame = true;
                        break;
                    }
                }
            }
            if (!isSame) {
                //如果都木有
                for (int j = 0; j < p1l.length; j++) {
                    lanCount[p1l[j]]++;
                }
                for (int j = 0; j < p2l.length; j++) {
                    lanCount[p2l[j]]++;
                }
            }
        }
        //此时找到了
        return len;
    }
}
